#include<vector>
#include<string>
#include<algorithm>
using namespace std;

int numDistinct(string s, string t) {
    int n = s.size(), m = t.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    s = " " + s;
    t = " " + t;
    for (int i = 0; i <= n; i++)
        dp[0][i] = 1;
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            dp[i][j] = t[i] == s[j] ? dp[i - 1][j - 1] + dp[i][j - 1] : dp[i][j - 1];
        }
    }
    return dp[m][n];
}

bool isMatch(string s, string p) {
    int m = s.size(), n = p.size();
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
    s = " " + s;
    p = " " + p;
    dp[0][0] = true;
    for (int j = 1; j <= n; j++)
    {
        if (p[j] == '*') dp[0][j] = true;
        else break;
    }
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (p[j] == '?')
            {
                dp[i][j] = dp[i - 1][j - 1];
            }
            else if (p[j] == '*')
            {
                dp[i][j] = dp[i][j - 1] || dp[i - 1][j - 1] || dp[i - 1][j];
            }
            else
            {
                if (s[i] == p[j]) dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    return dp[m][n];
}

bool asteroidsDestroyed(double mass, vector<int>& asteroids) {
    vector<int> min, max;
    for (auto x : asteroids)
    {
        if (x <= mass) min.push_back(x);
        else max.push_back(x);
    }
    sort(min.begin(), min.end(), greater<int>());
    sort(max.begin(), max.end(), less<int>());
    for (auto x : min) mass += x;
    for (auto x : max)
    {
        if (mass >= x) mass += x;
        else return false;
    }
    return true;
}

int main()
{
    numDistinct("babgbag", "bag");
    isMatch("babgbag", "bag");

    vector<int> v{ 3,9,19,5,21 };
    int mass = 10;
    /*sort(v.begin(), v.end(), [](int v1, int v2)
        {
            return 
        });*/
    asteroidsDestroyed(10, v);

	return 0;
}